package cn.z2huo.algorithm.binarytree;

import java.util.ArrayDeque;
import java.util.Deque;

// 二叉树的中序遍历
public class Traversal_LDR {
    // 递归中序遍历二叉树
    public void recurse(TreeNode root){
        if(root!=null){
            if(root.getLeft()!=null){
                recurse(root.getLeft());
            }
            System.out.print(root.toString()+" ");
            if(root.getRight()!=null){
                recurse(root.getRight());
            }
        }
    }

    // 迭代，利用栈中序遍历二叉树
    public void iterate(TreeNode root){
        Deque<TreeNode> stack = new ArrayDeque();
        TreeNode node = root;
        while(node!=null || !stack.isEmpty()){
            if(node!=null){
                stack.push(node);
                node = node.getLeft();
            }else{
                node = stack.pop();
                System.out.print(node.toString()+" ");
                node = node.getRight();
            }
        }
        System.out.println();
    }
}
